package bit_operation;

public class OddTimesNum {

    /**
     * 0 ^ n = n
     * 一个数组中，有一种数字出现了奇数次，其他数都出现了偶数次，如何找到，并打印出这种数？
     * 
     * @param arr
     * @return
     */
    public static void getOddNumberOfOccurrences(int[] arr) {
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            result ^= arr[i];
        }
        System.out.println(result);
    }

    /**
     * 一个数组中，有两种数字出现了奇数次，其他数都出现了偶数次，如何找到，并打印出这两种数？
     * 
     * @param arr
     * @return
     */
    public static void getOddNumberOfOccurrences2(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // a 和 b 是两种数
        // eor != 0
        // eor最右侧的1提取出来
        // eor : 00011101001000
        // rightOne : 00000000001000
        int rightOne = eor & ((~eor) + 1);// 提取最右侧的1
        int onlyOne = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & rightOne) != 0) {
                onlyOne ^= arr[i];
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 1, 1, 2, 1, 2, 2, 2 };
        int[] arr2 = { 1, 2, 1, 1, 2, 1, 2, 3 };
        getOddNumberOfOccurrences(arr);
        getOddNumberOfOccurrences2(arr2);

    }

}
